10166. Max-heap
Given array of integers.
Rearrange its elements so that to get a max-heap.
Input. First line contains number of elements n (n ≤ 1000).
Second line contains n integers.
Output. Print array that corresponds to max-heap.
|
Sample input |
Sample output |
|
6 5 3 2 7 1 10 |
10 7 5 3 1 2 |
SOLUTION
heap
Algorithm
analysis
Read the input data into array
à. For all indexes of array from n / 2 downto 1 execute the procedure heapify. Array
turns into max-heap.
Example
The
original array and the final array that is a
heap are shown below.
Algorithm
realization
Declare the array,
which later will be converted into a heap.
#define MAX 1001
int a[MAX];
Function left returns the index of the
left sun.
int left(int i)
{
return 2 * i;
}
Function right returns the index of the
right sun.
int right(int i)
{
return 2 * i + 1;
}
Function swap swaps the elements i and j.
void swap(int &i, int &j)
{
int temp = i; i = j; j = temp;
}
Function heapify restores
the heap property for the tree with the root
in the i-th vertex. Third parameter n is the size of the heap maintained.
void heapify(int a[], int i, int n)
{
int largest = 0;
int l = left(i);
int r = right(i);
We are looking for the index of the maximum element
among the current a[i] and its sons
a[l] and a[r].
if (l <= n
&& a[l] > a[i]) largest = l;
else largest = i;
if (r <= n
&& a[r] > a[largest]) largest = r;
If a[i] is
not the maximum element, then we change it with the maximum one and then
recursively restore the heap property in the left or right subtree.
if (largest != i)
{
swap(a[i], a[largest]);
heapify(a, largest, n);
}
}
The main part of the program. Read the input array starting from index 1.
scanf("%d", &n);
for (i = 1; i <= n; i++)
scanf("%d", &a[i]);
For all indexes from n / 2 to 1 execute the heapify procedure.
for (i = n / 2; i > 0; i--)
heapify(a, i, n);
Print the
resulting array, which is the max-heap.
for (i = 1; i <= n; i++)
printf("%d
", a[i]);
printf("\n");
Java realization
import java.util.*;
public class Main
{
static int left(int i)
{
return 2 * i;
}
static int right(int i)
{
return 2 * i + 1;
}
static void swap(int a[], int i, int j)
{
int temp = a[i]; a[i] = a[j]; a[j] = temp;
}
//max - heap
static void heapify(int a[], int i, int n) // n = size
of a heap
{
int largest = 0;
int l = left(i);
int r = right(i);
if (l <= n && a[l] > a[i]) largest = l;
else largest = i;
if (r <= n && a[r] > a[largest]) largest = r;
if (largest != i)
{
swap(a, i, largest);
heapify(a, largest, n);
}
}
public static void main(String[] args) {
Scanner con = new Scanner(System.in);
int n = con.nextInt();
int m[] = new int[n+1];
for(int i = 1; i <= n; i++)
m[i] = con.nextInt();
for(int i = n / 2; i > 0; i--)
heapify(m,i,n);
for(int i = 1; i <= n; i++)
System.out.print(m[i] + " ");
System.out.println();
con.close();
}
}